/*
 * @lc app=leetcode.cn id=15 lang=javascript
 *
 * [15] 三数之和
 *
 * https://leetcode-cn.com/problems/3sum/description/
 *
 * algorithms
 * Medium (20.34%)
 * Total Accepted:    35.5K
 * Total Submissions: 173.2K
 * Testcase Example:  '[-1,0,1,2,-1,-4]'
 *
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0
 * ？找出所有满足条件且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 *
 * 满足要求的三元组集合为：
 * [
 * ⁠ [-1, 0, 1],
 * ⁠ [-1, -1, 2]
 * ]
 *
 *
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  nums.sort()
  const result = []
  let zeroFlag = 0
  nums.forEach((n, idx) => {
    if (n === 0) {
      zeroFlag++
      return
    }
    if (n > 0) return
    const two = twoSum(nums.slice(idx + 1), -n)
    result.push(...two.map(tmp => [...tmp, n]))
  })
  tmp = []
  result.forEach(a => {
    a.sort()
    if (!tmp.some(t => t[0] === a[0] && t[1] === a[1])) {
      tmp.push(a)
    }
  })
  if (zeroFlag >= 3) {
    tmp.push([0, 0, 0])
  }
  return tmp
}

function twoSum(arr, sum) {
  const result = []
  if (arr.indexOf(sum / 2) !== arr.lastIndexOf(sum / 2)) {
    result.push([sum / 2, sum / 2])
  }
  const cache = new Set(arr)
  arr.forEach((n, idx) => {
    // 跟前一位比较，重复的数字就不用再次比较了
    if (idx > 0 && n === arr[idx - 1]) {
      return
    }
    cache.delete(n)
    if (cache.has(sum - n)) {
      result.push([n, sum - n])
    }
  })
  return result
}
console.log(threeSum([-1, 0, 1, 2, -1, -4]))
